The present invention pertains, in general, to shared resources, and more particularly to a system and method for arbitrating access to a shared resource among a plurality of entities.
Contemporary computing and communication systems often utilize one or more shared resources in an effort to streamline the system. Examples of shared resources can include a shared bus or other communications channels, shared peripherals, shared memory, and so on. Depending on the nature of the shared resource and the system in which it is implemented, different techniques can be employed to manage the use of that resource among the various system entities. For example, where multiple computers or workstations share one or more common printers, printer queues can be established such that when print jobs are received, they are queued and handled in order. As another example, Ethernet(copyright) and other network protocols provide features such as collision detection and packet retransmission to allow multiple computing systems to share the common network.
In other scenarios it is not desired or not practical to share resources in this manner. For example, many bus architectures do not provide collision detection and retransmission features. Instead, these architectures rely on schemes referred to as bus arbitration to determine which of a plurality of processors or other entities are granted access to the bus. In most instances, arbitration is performed among the competing entities to determine which entity will get exclusive access to the bus or other resource for an upcoming time slot.
One aspect of the invention, comprises a shared memory system that includes a centrally located memory. The shared memory can have a plurality of storage locations, each for storing data of a finite data size as a block of data. The block of data is accessible by an address associated with the storage location for that block of data. In one embodiment, the centrally located memory is controlled by a memory access control device. In one embodiment, the centrally located memory is physically provided in a centralized location. In an alternative embodiment, the centrally located memory can be physically distributed among one or more entities, while having common addressing. In this manner, even though the memory is physically distributed, the common addressing provides a memory that is centralized virtually, if not physically. In either embodiment, the memory is referred to as centrally located memory.
A plurality of peripheral devices can be disposed remote to the shared memory system. One or more of these devices can be configured to access the centrally located memory and generate addresses to address memory locations in the centrally located memory system. In this manner, the peripheral device can transfer data thereto or retrieve data therefrom. A memory interface device can be provided between each of the peripheral devices and the centrally located memory system to control the transmittal of addresses from the associated peripheral device to the centrally located memory and the transfer of data therebetween. In one embodiment, the memory interface device has a unique ID, which is transmitted to the centrally located memory.
According to another aspect of the invention, a portion of the centrally located memory is reserved or used for controlling peripheral devices or other entities having access to the memory. For example, in one embodiment, common address space is reserved, to which values can be written, wherein the values written can be used to control functions for the various entities. For example, these values can control parameters such as device priority, processor reset, interrupts, polling ID, fair bit and so on. In this embodiment, a processor or entity can write a value to a memory location associated with another processor or entity. More specifically, one processor can use this write operation to write a value to a particular memory location to change one or more parameters of one or more other processors.
In one embodiment, an arbitration device is associated with the centrally located memory. The arbitration device can be used to determine which of the peripheral devices is granted access to the centrally located memory. In one embodiment, the centrally located arbitration device is used to allow a host process to arbitrate for access to the centrally located memory, and a distributed arbitration scheme is used to allow peripheral processors.
In one embodiment, the arbitration device operates on a block-by-block basis to allow each peripheral unit to access the centrally located memory for a block of data before relinquishing access. In one aspect of this embodiment, wherein all requesting ones of the peripheral devices will have access to at least one block of data prior to any of the peripheral devices having access to the next block of data requested thereby.
In an alternative embodiment of the invention, each block of data comprises a unit of data. This unit can be, for example, a bit, a byte, a word, or other unit of data. Further, each memory interface device is given a priority value based upon its priority and/or its unique ID. The arbitration device operates in a second mode to allow the highest priority one of the requesting peripheral devices to seize the bus away from any of the other peripheral devices to access all of the data requested thereby. In one embodiment, the device ID is used to break ties that may arise on priority contests based solely on device priority.
According to another aspect of the invention, an arbitration system and method provides self-arbitration among a plurality of processors or other entities vying for access to the bus or other shared resource. In this embodiment, the entities vying for access to the shared resource present their respective priority values to an evaluation medium. The evaluation medium determines the highest priority value of those values presented, and provides this xe2x80x9cwinningxe2x80x9d value to the competing entities. The entities compare the received xe2x80x9cwinningxe2x80x9d value to their respective presented values. If an entity makes a positive comparison, that entity won the arbitration and is granted access to the shared resource. This arbitration technique can be used for any implementation in which two or more entities are vying for access to one or more shared resources, and is particularly useful in the context of the present description in which two or more processors are competing for access to a system bus, with or without bus memory.
Further features and advantages of the invention as well as the structure and operation of various embodiments of the invention are described in detail below with reference to the accompanying drawings.